package 中等.动态规划;

import java.util.Scanner;

/**
 * 描述
 * Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，
 * 从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，
 * 你能替Redraiment研究他最多走的步数吗？
 * 数据范围：每组数据长度满足 1 \le n \le 200 \1≤n≤200  ，
 * 数据大小满足 1 \le val \le 350 \1≤val≤350
 * <p>
 * 输入描述：
 * 数据共2行，第1行先输入数组的个数，第2行再输入梅花桩的高度
 * <p>
 * 输出描述：
 * 输出一个结果
 */
public class Redraiment的走法 {

    /**
     * 动态规划
     * 子问题：
     * dp[i] 表示以 i 为起点的最长步数是多少
     * 分析：
     * 逆序遍历数组，遍历到索引 i 时，需要寻找 [i+1,arr.length-1] 中
     * 所属符合 arr[i] < arr[j] 的 j 索引
     * 状态转移方程：
     * dp[i] = math.max(dp[i],dp[j]+1)
     * 注意：
     * 遍历过程中维护 dp[i] 的最大值
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.nextLine();

        int max = 0;
        String str = sc.nextLine();
        String[] strArr = str.split(" ");
        int[] dp = new int[strArr.length];
        for (int i = strArr.length - 1; i >= 0; i--) {
            int r = i + 1;

            dp[i] = 1;
            while (r < strArr.length) {
                if (Integer.valueOf(strArr[i]) < Integer.valueOf(strArr[r])) {
                    dp[i] = Math.max(dp[i], dp[r] + 1);
                }
                r++;
            }

            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }

}
